package com.cqs.leetcode;

import java.util.*;

/**
 * Author:li
 * <p>
 * create date: 18-6-1 21:01
 */
public class Permutations46 {


    /**
     * 思想:
     * 先全排列nums[0]得到全排列A0
     * 在全排列A0的基础上排列nums[0,1]
     * ...
     * 在全排列An_2的基础上排列nums[0,....,n-1]
     *
     * @param nums
     * @return
     */
    // 7ms 66.4%
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length > 0) {
            List<Integer> init = new ArrayList<>();
            init.add(nums[0]);
            result.add(init);
            Stack<List<Integer>> stack = new Stack<>();
            for (int i = 1; i < nums.length; i++) {
                while (result.size() != 0) {
                    stack.push(result.remove(0));
                }
                while (stack.size() != 0) {
                    List<Integer> pop = stack.pop();
                    //将nums[i]插入到可能的位置
                    for (int j = 0; j < pop.size(); j++) {
                        List<Integer> list = new ArrayList<>(pop);
                        list.add(j, nums[i]);
                        result.add(list);
                    }
                    pop.add(pop.size(), nums[i]);
                    result.add(pop);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Permutations46 permutation = new Permutations46();
        int[] nums = {1, 2, 3};
        List<List<Integer>> permute = permutation.permute(nums);
        System.out.println(permute);
    }


    //lettcode 5ms
    private static class Solution1 {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> cur = new ArrayList<>();
            permuteCore(result, cur, nums, 0);
            return result;
        }

        private void permuteCore(List<List<Integer>> result, List<Integer> cur, int[] nums, int index) {
            if (index == nums.length) {
                result.add(new ArrayList<>(cur));
                return;
            }

            for (int i = index; i < nums.length; i++) {
                swap(nums, i, index);
                cur.add(nums[index]);
                permuteCore(result, cur, nums, index + 1);
                cur.remove(cur.size() - 1);
                swap(nums, index, i);
            }
        }

        private void swap(int[] a, int i, int j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }


        public static void main(String[] args) {
            Solution1 silution = new Solution1();
            int[] nums = {1, 2, 3};
            List<List<Integer>> permute = silution.permute(nums);
            System.out.println(permute);
//        System.out.println(permuteUnique.size() == Math.pow(nums.length, nums.length));
        }
    }


    //6ms leetcode
    private class Solution2 {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            boolean[] isVisited = new boolean[nums.length];
            List<Integer> level = new ArrayList<>();
            DFS(nums, isVisited, level, result);
            return result;
        }

        public void DFS(int[] nums, boolean[] isVisited, List<Integer> level, List<List<Integer>> result) {
            if (level.size() == nums.length) result.add(new ArrayList<Integer>(level));
            for (int i = 0; i < nums.length; i++) {
                if (isVisited[i]) continue;
                isVisited[i] = true;
                level.add(nums[i]);
                DFS(nums, isVisited, level, result);
                level.remove(level.size() - 1);
                isVisited[i] = false;
            }
        }
    }


    //19ms beat 4.8%
    private static class Solution {
        private List<List<Integer>> result = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {
            if (nums == null || nums.length == 0) return result;
            HashSet<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }
            next(new ArrayList<>(), set);
            return result;
        }

        private void next(List<Integer> list, Set<Integer> set) {
            if (set.size() == 0) {
                result.add(list);
            } else {
                for (Integer integer : set) {
                    Set<Integer> ns = new HashSet<>(set);
                    ns.remove(integer);
                    List<Integer> nl = new ArrayList<>(list);
                    nl.add(integer);
                    next(nl, ns);
                }
                list.clear();
            }
            set.clear();
        }

        public static void main(String[] args) {
            Solution silution = new Solution();
            int[] nums = {1, 2, 3};
            List<List<Integer>> permute = silution.permute(nums);
            System.out.println(permute);
//        System.out.println(permuteUnique.size() == Math.pow(nums.length, nums.length));
        }
    }
}
